﻿//https://leetcode.cn/problems/copy-list-with-random-pointer/?envType=problem-list-v2&envId=hash-table

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head)
    {
        Node* copyhead = nullptr, * copytail = nullptr;
        Node* cur = head;
        unordered_map<Node*, Node*> hash;
        while (cur)
        {
            Node* node = new Node(cur->val);
            if (copyhead == nullptr)
            {
                copyhead = node;
                copytail = node;
            }
            else
            {
                copytail->next = node;
                copytail = node;
            }
            hash.insert({ cur,node });
            cur = cur->next;
        }

        Node* copy = copyhead;
        cur = head;
        //随机链表的复制
        while (cur)
        {
            if (cur->random == nullptr) copy->random = nullptr;
            else
            {
                copy->random = hash[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;

    }
};